package com.zq.solution.algorithm.dynamicProgramming;

/**
 * @ClassName Massage
 * @Description 动态规划——按摩师预约
 * 题目描述：
 *  一个有名的按摩师会接收到源源不断的预约请求，每个预约都可以选择接或者不接。在每次预约服务之间都需要休息时间，因此不能接受相邻的预约。
 *  给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
 * 示例1：
 *  输入：[1,2,3,1]
 *  输出：4
 *  解释：选择1号和三号预约时间最长，总时长 = 1 + 3 = 4；
 * 示例2：
 *  输入：[2,1,4,5,3,1,1,3]
 *  输出：12
 *  解释：选择1，3，5，8号续约，总时长为：2 + 4 + 3 + 3 = 12
 * @Author ZQ
 * @Date 2020/12/9 14:16
 * @Version 1.0
 */
public class Massage {
    public static int massage(int[] arr){
        if (arr == null || arr.length == 0) return Integer.MIN_VALUE;
        int length = arr.length;
        if (length == 1) return arr[0];
        int[][] dp = new int[length][2];//0不接，1接
        dp[0][0] = 0;
        dp[0][1] = arr[0];
        for (int i = 1; i < length; i++){
            dp[i][0] = Math.max(dp[i - 1][1],dp[i - 1][0]);
            dp[i][1] = dp[i - 1][0] + arr[i];
        }
        return Math.max(dp[length - 1][0],dp[length - 1][1]);
    }

    public static void main(String[] args) {
        System.out.println(massage(new int[]{2,1,4,5,3,1,1,3}));
    }
}
